1. Field of the Invention
The invention relates to a method for the production of an error correction parameter associated with the implementation of modular operations according to the Montgomery method. This method enables the performance of modular computations in a finite field (or Galois field) denoted GF(2.sup.n) without the performance of divisions.
2. Discussion of the Related Art
Conventionally, modular operations on GF(2.sup.n) are used in cryptography for applications such as the authentication of messages, the identification of a user and the exchange of keys. Such exemplary applications are described for example in the French patent application published under No. 2 679 054.
There are commercially available integrated circuits dedicated to such applications. These include, for example the product referenced ST16CF54 manufactured by SGS-THOMSON MICROELECTRONICS S.A., built around an association of the type comprising a central processing unit and an arithmetic coprocessor and dedicated to the performance of modular computations. The coprocessor used enables the processing of modular operations by the use of the Montgomery method. It is the object of a European patent application filed under the reference No. 0 601 907 A2, and is illustrated in FIG. 1 (this figure corresponds to FIG. 2 of the European patent application referred to). This document shall hereinafter be called the document D2.
The basic operation, called a P.sub.field operation, consists of the production, on the basis of three binary data elements A (multiplicand), B (multiplier) and N (modulo) encoded on an integer of bits n, of a binary data element denoted P(A, B).sub.N encoded on n bits, such that P(A, B).sub.N =A*B*I mod N, with I as a binary data element encoded on n bits such that I=2.sup.-n mod N. For this purpose, the data elements are considered to be encoded on m words of k bits, with m*k=n, and the words of the data elements A and B are given to a multiplication circuit having a series input, a parallel input and a series output.Specialized coprocessors, for example the coprocessor described in the document D2, are capable of carrying out all the conventional modular operations for a given size n=m*k bits. Furthermore, it is possible to use these processors as multipliers of k*m' bits, m' being a positive integer smaller than m. This amounts to stating that it is possible to carry out elementary P.sub.field operations on numbers with sizes greater than what can be normally processed by the coprocessor.
It has been seen here above that P(A, B).sub.N =A*B*I mod N, where I is in fact an error due to the subdivision into words of k bits. If it is desired to carry out a modular operation, for example a multiplication, it is necessary to eliminate this error term. For this purpose, a P.sub.field operation is carried out with an error correction parameter H equal to 2.sup.2*m*k when N is encoded on m words of k bits. In a coprocessor which may manage all the numbers of m*k bits, there is provided a wired circuit capable of performing this computation at high speed. However, if a size of number greater than the size of the computation registers is used, the computation of this error correction parameter has to be done on a more standard processor by a method that is identical but programmed, and therefore slower.